4、飞机降落

题目 飞机降落

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=15;

struct planes{

    int t,d,l;

}p[N];

bool st[N];

int T,n;

// int ans[N];

void dfs(int u,int last,bool &success){

    if(u>n){

        //for(int i=1;i<=n;i++)   cout<<ans[i]<<" ";cout<<endl;

        success=true;

        return;

    }

    for(int i=1;i<=n;i++){//u位置能放哪架飞机

        int t=p[i].t,d=p[i].d,l=p[i].l;

        if(t+d>=last && !st[i]){//如果该飞机的最晚降落时间晚于last 就说明可以放

            st[i]=true;

            // ans[u]=i;

            dfs(u+1,max(last,t)+l,success);

            st[i]=false;

        }

    }

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>T;

    while(T--){

        cin>>n;

        for(int i=1;i<=n;i++){

            int t,d,l;

            cin>>t>>d>>l;

            p[i]={t,d,l};

        }

        memset(st,0,sizeof st);

        bool success=false;

        dfs(1,0,success);

        if(success)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 3、冶炼金属 🏠 00-刷题理模型 ➡️ 5、接龙序列